package com.example.array.doublepointer;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
 *
 *  示例 1:
 * 输入：nums = [1,3,1], k = 1
 * 输出：0
 * 解释：
 * 所有数对如下：
 * (1,3) -> 2
 * (1,1) -> 0
 * (3,1) -> 2
 * 因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
 */
public class Leetcode719_SmallestDistancePair {
    public static void main(String[] args) {
        int[] nums = {1, 3, 6, 7, 9, 13};
        int k = 3;
        System.out.println(new Solution().smallestDistancePair(nums, k));
    }

    static class Solution {

        /**
         * 解法二:二分查找 + 双指针
         * 由于第 k 小的距离一定在 [0,  high = max(nums) - min(nums)] 中，我们在这个区间上进行二分。
         * 对于当前二分的位置 mid，统计距离小于等于 mid 的距离对数量用count表示(双指针实现)。
         * 如果count > k 则从(mid + 1, high)继续二分查找
         * 如果count < k 则从(low, mid - 1)继续二分查找
         * 如果count = k 则返回mid的值
         *
         * @param nums
         * @param k
         * @return
         */
        private int smallestDistancePair2(int[] nums, int k) {
            // 首先把数组进行排序，方便进行二分查找
            Arrays.sort(nums);
            // low: 数组中两个数相差的最小值，high: 数组中两个值可能相差的最大值
            int low = 0, high = nums[nums.length - 1] - nums[0];

            while (low < high) {
                int mid = low + (high - low) / 2;// 找到差值的中间值，并尝试以 mid 来看是不是差值小于等于 mid 的数对个数符合要求 k
                int count = 0, left = 0;// count: 统计所有的符合要求的情况，left: 标记循环遍历整个数组的左边界

                // 统计距离小于等于 mid 的距离对数量
                for (int right = 0; right < nums.length; ++right) {
                    // 在循环过程中，如果 nums[right] - nums[left] 大于了 mid，说明 left 太小了，这时候增大 left就可以使得数量减少
                    while (nums[right] - nums[left] > mid) ++left;
                    // 左右指针之间的数对都符合 nums[right] - nums[left] <= mid的要求
                    count += right - left;
                }

                if (count >= k) // 如果符合差值小于等于 mid 的数对个数太多了（count >= k） 那么就减小最高值
                    high = mid;
                else // 否则说明数对个数太少了，需要加大阈值 mid
                    low = mid + 1;
            }
            // 到最后 low 就是最小的差值
            return low;
        }

        /**
         * 解法一:堆(超时)
         * 将数组排序，此时对于固定的下标 i，从小到大的距离分别为 (i, i + 1)，(i, i + 2)，...，(i, N - 1)。
         * 因为 (i, j + 1) 的距离不会小于 (i, j)，因此只要 (i, j) 还在堆中，就没有必要把 (i, j + 1) 放入堆中。
         *
         * 然后将所有 (i, i + 1) 放入堆中，
         * 然后每次取出堆中的最小元素 (i, j) 时（元素的大小为 nums[j] - nums[i]，即距离），再把 (i, j + 1) 放入堆中。
         * 直到取出 k 个元素，就得到了第 k 小的距离。
         *
         *
         * @param nums
         * @param k
         * @return
         */
        private int smallestDistancePair1(int[] nums, int k) {
            Arrays.sort(nums);// 排序后的数组(i, i + 1)的距离一定是小于(i, i + 2 ....)
//            Queue<Positions> maxHeap = new PriorityQueue<>((p1, p2) ->
//                    (nums[p1.next] - nums[p1.cur]) - (nums[p2.next] - nums[p2.cur]));
            // 下面的写法等效于上面的写法
            Queue<Positions> minHeap = new PriorityQueue<>(Comparator.comparingInt(p -> nums[p.p2] - nums[p.p1]));

            // 将(i, i + 1)全部放入堆中
            for (int i = 0; i < nums.length - 1; i++) {
                minHeap.offer(new Positions(i, i + 1));
            }

            Positions tmp = null;
            while (k > 0) {
                tmp = minHeap.poll();
                if (tmp.p2 + 1 < nums.length) minHeap.offer(new Positions(tmp.p1, tmp.p2 + 1));
                --k;
            }

            return nums[tmp.p2] - nums[tmp.p1];
        }

        // 记录在nums中的索引值
        class Positions {
            int p1; //
            int p2;

            public Positions(int p1, int p2) {
                this.p1 = p1;
                this.p2 = p2;
            }
        }

        public int smallestDistancePair(int[] nums, int k) {
            return smallestDistancePair2(nums, k);
        }
    }
}
